#!/usr/bin/python
# Filename: Sort.py

# Sort
# every sort function has a parameter cmp for self-defined compare
# the compare function must return -1, 0, or 1 when relation between to object is less, equal, or greater
# common compare is function cmp(a, b), we don't use diff bcz there may be no "-" method in target object
# but ">", "==", "<" can be defined in target object
# stable sort: if Ki(Key of Node i) = Kj, i<j, after sort, Node i is still before Node j

def swap(array, i, j):
    array[i], array[j] = array[j], array[i]

def insert_sort(array, cmp=cmp):
    # insert a new element into the already-in-order array before it
    # for short sequence, insert sort is more efficient
    # for partially ordered sequence, insert sort is efficient
    length = len(array)
    for i in range(1, length):
        # 1) insert by swap
        #for j in range(i, 0, -1):
        #    if cmp(array[j], array[j-1]) == -1:
        #        swap(array, j, j-1)
        #    else: break
        # insert by move
        temp = array[i]
        j = i-1
        while (j >= 0) and (cmp(temp, array[j]) == -1):
            array[j+1] = array[j]
            j -= 1
        array[j+1] = temp
        # add ph array[0] = array[i] to remove j >= 0 test
        # array[1:] is the array to be sorted
    # time complexity:
    # compare O(n^2)
    # swap O(n^2)
    # best O(n) compare and no swap(or O(n) move)
    # stable

def binsert_sort(array, cmp=cmp):
    # find insert position by binary search
    length = len(array)
    for i in range(1, length):
        temp = array[i]
        left = 0
        right = i-1
        while left <= right:
            mid = (left+right)/2
            if cmp(array[i], array[mid]) == -1:
                right = mid-1
            else:
                left = mid+1
        # insert postion is left or right+1
        # insert by move
        for j in range(i, left, -1):
            array[j] = array[j-1]
        array[left] = temp
    # time complexity:
    # compare O(nlog(n))
    # move O(n^2)
    # best: O(nlog(n)) compare and O(n) move(if use swap, there can be no swap)
    # stable

def bubble_sort(array, cmp=cmp):
    # bubble is from end to top
    # end is fixed(length-1), top is increased from 0
    # each time, least between top and end is bubbled to top
    length = len(array)
    for i in range(length-1):
        j = length-1
        # unchanged flag
        # if unchanged, the sequence is already in order
        flag = True
        while j > i:
            if cmp(array[j], array[j-1]) == -1:
                swap(array, j, j-1)
                flag = False
            j -= 1
        if flag: break
    # time complexity:
    # compare O(n^2)
    # swap O(n^2)
    # best: O(n) compare and no swap

def sselect_sort(array, cmp=cmp):
    '''Straight Select Sort'''
    # select the least and swap it to the right place
    length = len(array)
    for i in range(length-1):
        j = i+1
        temp = i
        while j < length:
            if cmp(array[j], array[temp]) == -1:
                temp = j
            j += 1
        swap(array, i, temp)
    # time complexity
    # compare O(n^2)
    # swap O(n)
    # not stable, top greater values will change their order after sort

def shell_sort(array, shell=None, cmp=cmp):
    # shell sort is created bcz of insert sort's 2 advantage
    length = len(array)
    if length == 0: return # for log(length) safe

    def step_insert_sort(array, start, delta):
        # delta is the step of insert sort,
        # and this sort will happen delta times for range(0, delta) in array
        for i in range(start+delta, length, delta):
            j = i
            while j > start and cmp(array[j], array[j-delta]) == -1:
                swap(array, j, j-delta)
                j -= delta

    if shell == None:
        shell = []
        from math import log
        max = int(log(length)/log(2))-1
        while max > 1:
            shell.append(2**max-1)
            max -= 1
        shell.append(1)
    for i in shell: # i is delta
        for j in range(i):
            step_insert_sort(array, j, i)
    # time complexity:
    # shell of  2^n sequence is O(n^2)(about n^2/2 = 2^(n-1)*(2-1) + 2^(n-2)*(2^2-1) + 2^(n-3)*(2^3-1) + ...)
    # shell of 2^n - 1 sequence(default shell) is O(n^(3/2))
    # proper shell will cost only O(n)

def quick_sort(array, cmp=cmp, sp=None):
    # Algorithm:
    # 1) select a pivot
    # 2) divide sequence into L and R, L[i] < pivot, R[j] > pivot
    # 3) quick sort L and R

    def select_pivot(array, left, right):
        return (left+right)/2

    if sp == None: sp = select_pivot

    def partition(left, right):
        pivot = sp(array, left, right)
        swap(array, pivot, right)
        temp = array[right]
        i = left
        j = right
        while i != j:
            while i < j and cmp(array[i], temp) == -1: i += 1
            if i < j:
                array[j] = array[i]
                j -= 1
            while i < j and cmp(temp, array[j]) == -1: j -= 1
            if i < j:
                array[i] = array[j]
                i += 1
        array[i] = temp
        return i

    def sort(left, right):
        #if (right -left) <= 16: return
        if left >= right: return
        pivot = partition(left, right)
        sort(left, pivot-1)
        sort(pivot+1, right)

    length = len(array)
    sort(0, length-1)
    #insert_sort(array, cmp)

    # space complextiy:
    # worst O(n) (n partitions)
    # average and best O(log(n)) (approximate log(n) partitions)
    # time complexity:
    # worst O(n^2)
    # average and best O(nlog(n))
    # unstable
    # use insert sort to sort short sequences,
    # or do not sort short sequences, use insert sort on whole sequence at last
    # threshold 16 is the best
    # Random Quick Sort(RQS) using random pivot is often better

def merge_sort(array, cmp=cmp):
    # Algorithm:
    # divide -> recursive sort -> merge

    length = len(array)
    # temp_array is to keep space complexity O(n) when merge
    temp_array = [None] * length

    def part_insert_sort(left, right):
        for i in range(left+1, right+1):
            j = i
            while j > 0 and array[j] < array[j-1]:
                swap(array, j, j-1)
                j -= 1

    def merge(left, mid, right):
        # merge array[left:d] and array[d, right+1]
        temp_array[left:right+1] = array[left:right+1]
        i = left
        j = mid+1
        k = left
        while i != mid+1 and j != right+1:
            if temp_array[i] <= temp_array[j]:
                array[k] = temp_array[i]
                i += 1
            else:
                array[k] = temp_array[j]
                j += 1
            k += 1
        if i == mid+1: # array[left:d] is merged
            array[k:right+1] = temp_array[j:right+1]
        elif j == right+1: # array[d:right+1] is merged
            array[k:right+1] = temp_array[i:mid+1]

    def sort(left, right):
        #if (right-left) < 16:
        #    part_insert_sort(left, right)
        #    return
        if (right-left) < 1: return
        elif right - left == 1:
            if array[left] > array[right]: array[left], array[right] = array[right], array[left]
            return
        mid = (left+right)/2
        sort(left, mid)
        sort(mid+1, right)
        merge(left, mid, right)

    sort(0, length-1)
    # time complexity:
    # merge of each level is O(n)
    # total O(log(n)) levels
    # unstable
    # use insert sort to sort short sequence

def bucket_sort(array, key):
    # keys sequence which is corresponding to count must be in ascending order
    # to change this algorithm for descending order
    # just change second count[] to record how many items are bigger than current item
    length = len(array)
    temp_array = array[:]
    count = [0]*len(key)
    for i in array:
        count[key[i]] += 1
    for i in range(1, length):
        count[i] += count[i-1]
    # second count for descending order
    #for i in range(length-1, 0, -1):
    #    count[i-1] += count[i]
    for i in range(length-1, -1, -1):
        temp = temp_array[i]
        count[temp] -= 1
        array[count[temp]] = temp
    # time complexity:
    # O(n) + O(k) + O(n) = O(k+n)
    # stable

def radix_sort(array, keys, div):
    # radix sort is to use bucket sort many times for different domains(eg. digits of integer) with different keys
    # length of key(not keys) called r(radix), div is a function to get value of domain i for corresponding key i
    # to decide which is Most Significant Digit(Domain),
    # looks a in order sequence, which Domain is still in order.
    pass
    # time complexity:
    # MSD is just like divide-and-conquer
    # first key K0(MSD) cost K0 + O(n)
    # second key K1 cost K0*K1 + O(n)
    # third key K2 cost K0*K1*K2 + O(n) ...
    # LSD is commonly used
    # d = len(keys), number of keys
    # each key cost k + O(n), totally O(d(r+n))
    # stable

def simple_radix_sort(array, key, d):
    # in simple_radix_sort, all keys is the same
    # more simpler, key is just sequence of digits
    # r = len(key), d is number of domains of value in array
    # eg. for value between 1000 to 9999, d can be 4
    # use LSD to sort
    # linked radix sort reduce the space somplexity from d*n to n(nodes)+d*r(headers)(or n+r, if reuse headers)
    pass
    # time complexity:
    # still O(d(r+n))
    # stable

# Decision Tree of Sort:
# max leaf depth is just max compare times of sort in worst situation
# min is min in best situation
# 1) for n values, there will be n! leafs(sort result is one of the full arrangement)
# 2) depth of tree is no less than log(n!) = log(n^n) = nlog(n) (this minimal occurs when the tree is as balanced as possible)
# 2.1) eg. 4 leafs tree, least depth is log(4) = 2
# 3) so every sort method in worst situation needs nlog(n) times compare
# 4) for radix sort, nlog(n) is still right:
# 4.1) d > log(r)(n), so d(r+n) >= nlog(n). eg. for values between 0 to 9999, n <= 10000, r = 10, d = 4.

if __name__ == "__main__":
    a = [3, 2, 1, 4, 5, 10, 6, 7, 9, 8]
    def test_insert_sort():
        insert_sort(a)
        print a

    def test_binsert_sort():
        binsert_sort(a)
        print a

    def test_bubble_sort():
        bubble_sort(a)
        print a

    def test_sselect_sort():
        sselect_sort(a)
        print a

    def test_shell_sort():
        shell_sort(a)
        print a

    def test_quick_sort():
        quick_sort(a)
        print a

    def test_merge_sort():
        merge_sort(a)
        print a

    def test_bucket_sort():
        b = [3, 3, 2, 1, 4, 5, 1, 7, 4, 3]
        key = {}
        for i in range(10):
            key[i] = i
        bucket_sort(b, key)
        print b

    #print a
    #test_insert_sort()
    #test_binsert_sort()
    #test_bubble_sort()
    #test_sselect_sort()
    #test_shell_sort()
    #test_quick_sort()
    #test_merge_sort()
    test_bucket_sort()
